1. Field of the Invention
The present invention relates to a packet scheduling method and a packet scheduling apparatus for selectively outputting buffered packets in a packet network such as an ATM network.
2. Description of the Background Art
In a packet network based on an ATM (Asynchronous Transfer Mode) scheme, a packet in a fixed length of 53 octets called a cell is transmitted. In the ATM scheme, a connection is identified by identifiers called VCI (Virtual Channel Identifier) and VPI (Virtual Path Identifier) contained in a header section of a cell.
Also, the ATM scheme defines the service classes to which connections belong, including a CBR (Constant Bit Rate), a real time VBR (Variable Bit Rate), a non-real time VBR, ABR (Available Bit Rate), and UBR (Unspecified Bit Rate). Then, for each of these service classes, a QOS (Quality Of Service) regarding required cell loss rate and/or cell delay is specified. More specifically, the required values for both the cell loss rate and cell delay are specified for the service classes of CBR and real time VBR, whereas the required value for only the cell loss rate is specified for the service class of ABR and non-real time VBR, and no QOS is specified for the service class of UBR.
At a time of connection set up, a user reports parameters regarding traffic characteristics of a connection to a network, and the network sets up a connection if it is possible to guarantee the required QOS for this connection when it transmits cells without violating the reported parameters. For the reported parameters, a peak cell rate is used in a case of the service class of CBR, while a peak cell rate, an average cell rate, and a maximum burst length are used in the service classes of real time VBR and non-real time VBR.
It is necessary for the network to guarantee the QOS for a connection which is transmitting cells without violating the reported parameters, regardless of the other connections, even when there is another connection which is transmitting cells in violation to the reported parameters. To this end, there is a control called a UPC (Usage Parameter Control) which regulates inputs for a connection which is transmitting cells in violation to the reported parameters by monitoring a transmission rate of a connection at an entrance of the network. When this UPC is appropriately carried out, it is possible to guarantee the QOS for a connection which is transmitting cells without violating the reported parameters, regardless of the other connections, by managing cells of a plurality of connections at an ATM switch using a single or class by class FIFO (First-In First-Out) queues.
However, in a case where a cell rate by which a terminal can transmit cells varies dynamically while a connection is connected depending on a state of a network, such as a case of the service class of ABR, an accurate UPC is difficult to realize so that each connection tends to receive an influence from the other connection. In addition, the UPC is not supposed to be carried out for the service class of UBR, but it is preferable to carry out a control to use the bandwidth as evenly as possible among connections in the service class of UBR. Consequently, for the service class of ABR and/or UBR, there is a need to provide a queue for each connection and carry out the packet scheduling among a plurality of queues, instead of management using a single or class by class FIFO queues.
For this packet scheduling, a scheme called an FQ (Fair Queueing) scheme which provides services fairly at equal rates for all connections in a particular class has been proposed in: John B. Nagle, "On Packet Switches with Infinite Storage", IEEE Transactions on Communications, Vol. COM-35, No. 4, pp. 435-438, April 1987. This FQ scheme is realized by serving active (not vacant) queues in the round robin fashion, but this scheme is not appropriate when requested bandwidths are different for different connections. Moreover, there is a need to account for a packet length in a case of using packets in variable lengths.
For this reason, there are propositions for a packet scheduling scheme called a WFQ (Weighted Fair Queueing) which realizes the packet scheduling by giving weights to connections according to their utilization bandwidths, and providing services fairly at accordingly weighted rates while taking a packet length into account. As a specific algorithm for this WFQ scheme, an algorithm called an SCFQ (Self-Clocked Fair Queueing) has been proposed in: S. J. Golestani, "A Self-Clocked Fair Queueing Scheme for Broadband Applications", Proc. of IEEE INFOCOM '94, pp. 636-646, 1994, while a similar algorithm called a Virtual Clock has been proposed in: L. Zhang, "virtual Clock: A New Traffic Control Algorithm for Packet Switching Networks", Proc. of ACM SIGCOMM '90, pp. 18-29, 1990.
Now, assuming that the packet scheduling apparatus has a queue for each connection and a connection is to be identified by an identifier, according to the SCFQ, each connection i has a weight wi proportional to utilization bandwidth and a variable Fi, and when a packet arrives at the packet scheduling apparatus, a value of the variable Fi is updated and the updated variable Fi is stored into the queue along with the arrived packet. At a time of outputting packets, a packet of a connection having the smallest Fi value among the variables Fi of top packets in the active queues is served. Here, the variable Fi is updated by: EQU Fi=L/wi+max(Fi, v(ta))
where L is a packet length of the arrived packet, ta is an arrival time of the arrived packet, and v(ta) is a non-decreasing function called virtual time. In SCFQ, v(ta) returns a value of the variable Fj for a packet of a connection j which is being served or just finished being served at a time ta. In Virtual Clock, v(ta) is equal to ta.
However, the conventionally proposed packet scheduling scheme based on an algorithm such as SCFQ or Virtual Clock has the following two major problems.
The first major problem is that it is difficult to provide services fairly in a short time scale in a case of scheduling packets of connections with large weight differences. For instance, suppose that the queues corresponding to connections have total 101 pieces of packets including 100 pieces of packets for 100 pieces of connections with a weight value 1 and one piece of packet for one piece of connection with a weight value 100, and packets of the connection with a weight value 100 arrived consecutively in this state. To be completely fair, packets of 100 pieces of connections with a weight value 1 and packets of one piece of connection with a weight value 100 should be scheduled alternately, but in the SCFQ or Virtual Clock, at most 100 pieces of packets of the connection with a weight value 100 are outputted first, and then packets of the connections with a weight value 1 are outputted.
In other words, when a group of connections with a large weight value and a group of connections with a small weight value are present and a sum of weight values of the connections is the same for both groups, there is a problem in that the packets of the group of connections with a large weight value will be always favored in a short time scale, which results in an increase of delay jitter for connections with smaller weights even when the traffic load is small.
The second major problem is that a calculation time required in calculating the smallest value of the variable Fi at a time of the packet scheduling increases as a number of connections increases. Assuming that the variables Fi are always sorted, when a number of connections is n, a calculation time required in calculating the smallest value will be in the same order as a time for inserting a new Fi into a sequence of sorted Fi, i.e., an order of 0(log.sub.2 n). In a case of ATM, in order to support a maximum number of virtual connections (VC)=4096 per one physical link, it requires at most log.sub.2 (4096)=12 times of searches in calculating the smallest value of the variable Fi.
In view of this increase of the calculation time, and in consideration to a case of carrying out the scheduling not only for packets but also for classes and virtual paths (VP) or a case of a large link rate, the algorithm such as SCFQ and Virtual Clock is difficult to implement in practice, in this regard, there is a demand for the packet scheduling scheme in which the processing time required for the scheduling is short regardless of a number of connections.
On the other hand, U.S. Pat. No. 5,379,297 entitled "Concurrent Multi-Channel Segmentation and Reassembly Processors for Asynchronous Transfer Mode" discloses a scheme in which a queue is formed for each peak rate and the WFQ is carried out among a plurality of queues in the processing time which is independent of a number of connections. However, this scheme cannot support arbitrary combination of peak rates (weights).